import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mac
 * Date: 2022-09-25
 * Time: 8:57
 */
class TreeNode {
    public char val;
    public TreeNode left;//左孩子的引用
    public TreeNode right;//右孩子的引用

    public TreeNode(char val) {
        this.val = val;
    }

}
public class BinaryTree {
    public TreeNode root;//二叉树的根节点

    public TreeNode createTree() {//暂时写法
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }
    //二叉树的遍历，重点: 所有二叉树相关的题目，基本上都是需要通过某种遍历取解题的
    //1.前序遍历 2.中序遍历 3.后序遍历 4.层序遍历

    //1.前序遍历 根 -> 左子树 -> 右子树 ABDCEF

    //2.中序遍历 左子树 -> 跟 -> 右子树 DBAECF

    //3.后序遍历 左子树 -> 右子树 -> 根 DBEFCA

    //练习：前序：ABDEHCFG 中序：DBEHAFCG 后序：DHEBFGCA

    //二叉树的题天生就用递归来写的

    //知道前序和后序无法确定一颗二叉树

    //前序遍历
    void preOrder(TreeNode root) {//传入二叉树的根
        if (root == null){//判断根是否为空
            return;
        }
        System.out.print(root.val + " ");//打印节点信息
        preOrder(root.left);//递归遍历该根节点的左子树
        preOrder(root.right);//递归遍历该根节点的右子树
    }

    //中序遍历
    void inOrder(TreeNode root){//传入二叉树的根
        if (root == null){//判断根是否为空
            return;
        }
        inOrder(root.left);//递归遍历该根节点的左子树
        System.out.print(root.val + " ");//中序打印根节点
        inOrder(root.right);//递归遍历该根节点的右子树
    }

    //后序遍历
    void postOrder(TreeNode root){//传入二叉树的根
        if (root == null){//判断根是否为空
            return;
        }
        postOrder(root.left);//递归遍历该根节点的左子树
        postOrder(root.right);//递归遍历该根节点的右子树
        System.out.print(root.val + " ");//后序打印根节点
    }

    //节点个数

    //遍历
    public int count = 0;
    public int size1(TreeNode root){
        if (root == null){
            return 0;
        }
        count++;
        size1(root.left);
        size1(root.right);
        return count;
    }
    //子问题
    public int size2(TreeNode root){
        if (root == null){//判空
            return 0;
        }
        //递归遍历左右树
        return size2(root.left) + size2(root.right) + 1;
    }

    //叶子节点个数

    //子问题
    public int getLeafNodeCount1(TreeNode root){
        if (root == null){//判空则返回0
            return 0;
        }
        if (root.left == null && root.right == null){
            return 1;//叶节点返回1
        }
        //递归遍历左右树
        return getLeafNodeCount1(root.left) + getLeafNodeCount1(root.right);
    }

    //求第K层节点个数

    public int getLeafNodeCount2(TreeNode root, int k){
        if (root == null){//空返回0
            return 0;
        }
        if (k == 1){
            return 1;//递归访问k - 1后到达指定层数返回1
        }
        return getLeafNodeCount2(root.left, k - 1) + getLeafNodeCount2(root.right, k - 1);
    }

    //获取二叉树高度
    //时间复杂度O(n)，空间复杂度O(log2(n))
    public int getHight(TreeNode root){
         if (root == null){//判空
             return 0;
         }
         //尽量不要用三目运算符 - 比较左右树最大高度
         return Math.max(getHight(root.left),getHight((root.right))) + 1;
    }

    //检测value值是否存在
    public boolean find1(TreeNode root, char val){
        if (root == null){
            return false;
        }
        if (root.val == val) {
            return true;
        }
        return find1(root.left, val) || find1(root.right, val);
    }

    public TreeNode find2(TreeNode root, char val){
        if (root == null){//为空不存在返回null
            return null;
        }
        if (root.val == val){
            return root;//找到节点
        }
        TreeNode ret = find2(root.left, val);//遍历左树
        if (ret != null){
            return ret;
        }else{//左树为空，遍历右树
            return find2(root.right, val);
        }
    }

    //判断一棵树是否为完全二叉树
    public boolean  isCompleteTree(TreeNode root){
        if (root == null){//空树也为完全二叉树
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();//队列
        queue.offer(root);//根节点入队
        while (queue.peek() != null){
            TreeNode cur = queue.poll();
            if (cur != null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else{
                break;
            }
        }
        while (!queue.isEmpty()){
            if (queue.peek() != null){
                return false;
            }
            queue.poll();
        }
        return queue.isEmpty();
    }

    //层序遍历
    public void levelOrder(TreeNode root){
        if (root == null){
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (queue.peek() != null){
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");//打印每层节点
            if (cur != null){
                if (cur.left != null) {//不为空入队
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
        }
    }
}

